#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include <iostream>
#include <MyInclude/LinkQueue.h>

class BinaryTree
{
public:
    using ElementType = int;

    BinaryTree();
    ~BinaryTree();

    void Insert(const ElementType &element);
    void Remove(const ElementType &element);
    ElementType *Find(const ElementType &element);
    void show();

private:
    struct TreeNode
    {
        TreeNode(const ElementType &element) : data(element)
        {
            left = right = parent = nullptr;
        }
        ElementType data; // 数据域
        TreeNode *left;  // 左孩子
        TreeNode *right;   // 右孩子
        TreeNode *parent;  // 双亲
    };
    TreeNode *InsertNode(TreeNode *node, const ElementType &element);
    void PrevTravel(TreeNode *node);
    void MidTravel(TreeNode *node);
    void PostTravel(TreeNode *node);
    void Free(TreeNode *node);
    TreeNode *RemoveNode(TreeNode *node, const ElementType &element);
    TreeNode *GetMinNode(TreeNode *node);
    ElementType *FindNode(TreeNode *node, const ElementType &element);
    TreeNode *RotateRight(TreeNode *root);
    TreeNode *RotateLeft(TreeNode *root);
    TreeNode *RotateLeftRight(TreeNode *root);
    TreeNode *RotateRightLeft(TreeNode *root);
    int GetNodeHight(TreeNode *node);
    int LRDevition(TreeNode *node);
    TreeNode *root;
};


#endif